The present invention is a method for changing routing tables with the minimum amount of disruption to signals being transmitted over the network. In particular, the present invention relates to a method for informing routers on a network when a link or links will be unavailable at a future time so that the routing tables can be recalculated in advance.
In an heterogeneous environment, such as networks, a need for connection devices to inter-connect two or more links is essential. In this environment, the router is that device. As it's name implies, the router also serves as a routing switch-board. Routers connect two or more networks and forward data packets between them. A router is connected to at least two networks, commonly two local area networks (LANs) or wide area networks (WANs) or a LAN and its Internet Service Provider's (ISP's) network. The idea of a router is to move traffic in the form of data packets from one area to another as needed instead of having one large network. When data arrives from one of the segments, the router decides, according to it's routing table, the segment to which the data will be forwarded. Even though each of the routers' connections is to one physical network, that one network can connect to other networks through the use of other routers. This way, many networks can interconnect.
A router is actually a special computer which is dedicated to the task of interconnecting networks. It moves information from its source to its destination by selecting the most efficient path. Routing refers to the process of choosing the best path over which to send packets and how to cross multiple physical networks. This is the basis of all Internet communication. Routers are located at gateways (a node on a network where two or more networks connect) and communicate with each other using protocols such as the Border Gateway Protocol (BGP) or the Open Shortest Path First protocol (OSPF). Routers forward data packets between any two hosts using headers (units of information that precede a data object) and forwarding tables to configure the best path for the packets to travel. Routers examine the data destination address, extract the target network address from it, and decide (based on this network address) where to transfer the data.
Routers have two major functions: optimizing the routing paths and switching, i.e., the transport of packets over networks. A router uses a routing algorithm to determine the optimal path to the destination. These algorithms maintain routing tables which contain route information such as destination/next hop association. When a computer wants to send a packet over the net, it formats a packet with the router's physical address and the destination address (protocol address) of the target host. The router searches it's routing tables for the destination host. If there is no entry for the destination host, the router usually drops the packet. If there is an entry for the destination host, the router replaces the physical address with the next hop's address and retransmits the packet. The next hop isn't necessarily the ultimate destination host, it may be another router which performs the same routine again. A packet may “visit” several routers/hosts on its route, each time the physical address of its destination changes.
A router consists of a computer with at least two network interface cards supporting the Internet Protocol (IP). The router receives packets from each interface via a network interface and forwards the received packets to an appropriate output network interface. Received packets have all link layer protocol headers removed, and transmitted packets have a new link protocol header added prior to transmission. The router uses the information held in the network layer header (i.e., IP header) to decide whether to forward each received packet, and which network interface to use to send the packet. Most packets are forwarded based on the packet's IP destination address, along with routing information held within the router in a routing table. After the router determines which path to use, it can proceed with switching the packet. This means it accepts the packet on one interface and forwards it to another interface that is the next hop on the best path to the packet's destination.
The routing and filter tables resemble similar tables in link layer bridges and switches. Except, that instead of specifying link hardware addresses (Media Access Control (MAC) addresses), the router table specifies a network (IP addresses). The routing table lists known IP destination addresses with the appropriate network interface to be used to reach that destination. A default entry may be specified to be used for all addresses not explicitly defined in the table. A filter table may also be used to ensure that unwanted packets are discarded. The filter may be used to deny access to particular protocols or to prevent unauthorized access from remote computers by discarding packets to specified destination addresses.
A variety of metrics can be used to define the best path. Some routing protocols, such as Routing Information Protocol (RIP), use only one metric and that is hop count. And some routing protocols, such as IGRP, use a combination of metrics. The metrics most commonly used by routers are: (1) hop count—the number of routers that a packet must go through to reach its destination; (2) bandwidth—the data capacity of a link; (3) delay—the length of time to move the packet from the source to destination; (4) load—the amount of activity on a network resource; (5) reliability—the error rate of each network link; (6) ticks—the delay on a data link using IBM PC clock ticks; and (7) cost—an arbitrary value assigned by an administrator. The optimal route refers to the ability of the routing protocol to select the best route, or the least expensive route. The best route depends on the metrics and metric weightings used to make the calculation. For example, one routing protocol might use the number of hops and the delay, but might weigh the delay more heavily in the calculation. Thus, a route having more hops and shorter delays may be less expensive than a route having fewer drops and longer delays. Since routing protocols indicate how expensive it is to send a packet through a link, traffic in a network can be redirected by indicating that a certain link is extremely expensive (in terms of delay or bandwidth, for example). This will cause routers to calculate paths around an expensive link even though it is nominally available.
Most routers also have a serial connector known as the “Console Port” to which a terminal (or a modem) may be connected. This port is usually used to control the router configuration when the router is first installed. It may be the only port which is allowed to configure the filter table (used to prevent unauthorized access between the connected networks).
Newer applications, such as real-time gaming and voice-over-IP (VoIP), are much more sensitive to short outages in the network than older applications such as email, File Transfer Protocol (FTP), and Web browsing. Even an interruption of a fraction of a second is noticeable—and annoying—to users. Such interruptions can happen because of link or interface failures on routers. The network self-heals, but this takes a significant amount of time. Accordingly, there is a need for a method that enables a user to anticipate the routing changes in a network caused by the unavailability of a link and to reconfigure the routing tables in advance in order to minimize any disruption of the network.